// 2025/3/19
// https://leetcode.cn/problems/letter-combinations-of-a-phone-number/?envType=study-plan-v2&envId=top-100-liked
// 电话号码的字母组合

class Solution {
    public:
        vector<string> hash = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        string tmp;
        vector<string> ans;
    
        void dfs(string& digits, int pos)
        {
            if(pos == digits.size())
            {
                ans.emplace_back(tmp);
                return;
            }
    
            int num = digits[pos] - '0';
            int n = hash[num].size();
            for(int i = 0; i < n; i++)
            {
                tmp.push_back(hash[num][i]);
                dfs(digits, pos + 1);
                tmp.pop_back();
            }
        }
    
        vector<string> letterCombinations(string digits) {
            if(!digits.empty())
                dfs(digits, 0);
            return ans;
        }
    };